package datastructure.book.tujiesuanfa.queueastack.exercise.first;

import java.util.PriorityQueue;

/**
 * 有序整数列表中的中间值,如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值
 * 每个方法时间复杂度低于O(n)，可为log(n)
 * 例：
 * 插入顺序  3、2、1  中位数  2
 * 插入顺序  2、5、6、1、2、3  中位数  2.5  解释：1、2、2、3、5、6
 */
public class MedianFinder {

    private final PriorityQueue<Integer> firQueue = new PriorityQueue<>((x, y)->y-x);
    private final PriorityQueue<Integer> secQueue = new PriorityQueue<>();

    public MedianFinder() {

    }

    public void addNum(int num) {
        if (firQueue.size() == secQueue.size()) {
            secQueue.add(num);
            firQueue.add(secQueue.poll());
        } else {
            firQueue.add(num);
            secQueue.add(firQueue.poll());
        }
    }

    /**
     * 空，返回-1
     */
    public double findMedian() {
        if (firQueue.isEmpty()) {
            return -1;
        }
        if (firQueue.size() == secQueue.size()) {
            return (double) (firQueue.peek() + secQueue.peek()) / 2;
        } else {
            return firQueue.peek();
        }
    }
}
